package algorithm.easy;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: CheckPossibility665
 * @description: 给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
 *
 * 我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/non-decreasing-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/2/715:47
 * @since V1.0
 */
public class CheckPossibility665 {
    //每修改一次就验证
    public boolean checkPossibility(int[] nums) {
        if (nums.length<3){
            return true;
        }
        for (int i=0;i<nums.length-1;i++){
            if (nums[i]>nums[i+1]){
                int temp = nums[i];
                nums[i] = nums[i+1];
                if (isSort(nums)){
                    return true;
                }
                //复原
                nums[i] = temp;
                nums[i+1] = nums[i];
                return isSort(nums);
            }
        }
        return true;
    }

    public boolean isSort(int[] arr){
        for (int i=0;i<arr.length-1;i++){
            if (arr[i]>arr[i+1]){
                return false;
            }
        }
        return true;
    }


    public boolean 官方题解(int[] nums) {
        int n = nums.length, cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                cnt++;
                if (cnt > 1) {
                    return false;
                }
                if (i > 0 && y < nums[i - 1]) {
                    nums[i + 1] = x;
                }
            }
        }
        return true;
    }


}
